1429. First Unique Number
Medium

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

  • FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
  • int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
  • void add(int value) insert value to the queue.

 

Example 1:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

Example 2:

Input: 
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output: 
[null,-1,null,null,null,null,null,17]
Explanation: 
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 
[null,809,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1

 

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^8
  • 1 <= value <= 10^8
  • At most 50000 calls will be made to showFirstUnique and add.
Accepted
56.4K
Submissions
112K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Use doubly Linked list with hashmap of pointers to linked list nodes. add unique number to the linked list. When add is called check if the added number is unique then it have to be added to the linked list and if it is repeated remove it from the linked list if exists. When showFirstUnique is called retrieve the head of the linked list.
Show Hint 2
Use queue and check that first element of the queue is always unique.
Show Hint 3
Use set or heap to make running time of each function O(logn).

Average Rating: 4.62 (21 votes)

Premium

Solution


Approach 1: Brute Force

Intuition

The simplest solution for this problem is to create a queue as normal, and then search through it to find the first unique number.

We do this by looping through the items in the queue (starting from the oldest). For each item, we loop through the queue again, counting how many times it appears. If it only appears once, we stop and return it. If there are no items that appear only once, then we return -1.

Algorithm

We don't need to implement counting ourselves; we can use Collections.frequency(...) in Java, and .count(...) in Python.

Complexity Analysis

Let KK be the length of the initial array passed into the constructor. Let NN be the total number of items added onto the queue so far (including those from the constructor).

  • Time complexity :

    • constructor: O(K)O(K).

      We create a new copy of the passed in numbers; this has a cost of O(K)O(K) time to create.

    • add(): O(1)O(1).

      We perform a single append to a queue; this has a cost of O(1)O(1).

    • showFirstUnique(): O(N2)O(N^2).

      Counting how many times a given item appears in the queue has a cost of O(N)O(N). This is true even for the library functions we're using.

      In the worst case, we search through the entire queue without finding a unique number. At a cost of O(N)O(N) each time, this gives us a cost of O(N2)O(N^2).

  • Space complexity : O(N)O(N).

    The memory used is simply the total number of items currently in the queue.



Approach 2: Queue and HashMap of Unique-Status

Intuition

When given a data-structure-design question like this one, a good strategy is to start simple and identify where the inefficiencies are.

In Approach 1, we performed numerous count operations; each call to showFirstUnique() performed, in the worst case, NN count operations. At a cost of O(N)O(N) per count, this was expensive! These count-ups are also repetitive, and so should be our focus for optimization.

When deciding whether or not to return a particular number, all we need to know is whether or not that number is unique. In other words, we only want to know whether it has occurred "once", or "more than once". Seeing as numbers cannot be removed from the FirstUnique data structure, we know that once a particular number is added for the second time, that number will never again be unique.

So, instead of counting how many times a number occurred in the queue, we could instead keep a HashMap of numbers to booleans, where for each number that has been added, we're storing the answer to the question is this number unique?. We'll call it isUnique. Then, when FirstUnique.add(number) is called, one of three cases will apply:

  1. This particular number has never been seen before now. Add it to isUnique with a value of true. Also, add it to the queue.

  2. This particular number has already been seen by isUnique, with a value of true. This means that the number was previously unique (and is currently in the queue), but with this new addition, it no longer is. Update its value to false. Do not add it to the queue.

  3. This particular number has already been seen by isUnique, with a value of false. This means that it has already been seen twice before. We don't need to do anything, and shouldn't add it to the queue.

Then, instead of needing to perform "count" operations, the showFirstUnique() can simply look in isUnique for the information it needs.

Here is an animation showing how this works so far.

Current
1 / 26

This is a good start. However, you might have noticed another inefficiency while watching the animation: the 7 at the front needs to be stepped passed on every call to showFirstUnique(). As soon as the second 7 was added, though, this 7 was no longer unique, and so would never be the answer to a call to showFirstUnique() again (remember, this queue has no deletion operation). Therefore, there is no reason to leave it in the queue—we should remove it so that we don't keep looking at it.

But, where should we actually do these removals from the queue? In showFirstUnique(), or in add()?

  • If we do a removal in the add() method, we'll need to do an O(N)O(N) search of the queue to find the number, and then potentially another to remove it from the queue, (if you're chosen programming language even supports deletions from the middle of a queue!).

  • If we do the removal in the showFirstUnique() method, we might sometimes need to do lots of removals before we find a unique number to return. However, it will be faster across all calls to the data structure, because we didn't need to do a search to find the non-unique number like we would have with add(). We'll talk more about this in the time complexity section.

So, our best option is to do the removals in the showFirstUnique() method.

We should leave the number's value as false in isUnique, though. Like we said above, a number can never "become" unique again.

Here is an animation showing the full algorithm.

Current
1 / 19

Algorithm

Complexity Analysis

Let KK be the length of the initial array passed into the constructor.

Let NN be the total number of items added onto the queue so far (including those from the constructor).

  • Time complexity :

    • constructor: O(K)O(K).

      For each of the KK numbers passed into the constructor, we're making a call to add(). As we will determine below, each call to add() has a cost of O(1)O(1). Therefore, for the KK numbers added in the constructor, we get a total cost of KO(1)=O(K)K \cdot O(1) = O(K).

    • add(): O(1)O(1).

      We check the status of the number in a HashMap, which is an O(1)O(1) operation. We also optionally modify its status in the HashMap, which, again, is an O(1)O(1) operation.

      Depending on the status of the number, we add it to the queue, which is again, an O(1)O(1) operation.

      Therefore, we get an O(1)O(1) time complexity for the add() method.

    • showFirstUnique(): O(1)O(1) (amortized).

      For this implementation, the showFirstUnique() method needs to iterate down the queue until it finds a unique number. For each unique number it encounters along the way, it removes it. Removing an item from a queue has a cost of O(1)O(1). The total number of these removals we need to carry out is proportional to the number of calls to add(), because each add() corresponds to at most one removal that will ultimately have to happen. Then when we find a unique number, it is an O(1)O(1) operation to return it.

      Because the number of O(1)O(1) removals is proportional to the number of calls to add(), we say that the time complexity amortizes across all calls to add() and showFirstUnique(), giving an overall time complexity of O(1)O(1) (amortized).

      If you're not familiar with amortized time complexity, check out the Wikipedia page.

  • Space complexity : O(N)O(N).

    Each number is stored up to once in the queue, and up to once in the HashMap. Therefore, we get an overall space complexity of O(N)O(N).



Approach 3: LinkedHashSet for Queue, and HashMap of Unique-Statuses

Intuition

While an amortized time of O(1)O(1) will always be better than a non-amortized time of a higher complexity class, say, O(N)O(N), non-amortized O(1)O(1) would be even better. The downside of amortized time complexities is that while the average time per method call is "good", some calls might be really slow. Imagine if every one-millionth Google search took 1,000,000 ms, and all the others took 1 ms. The amortized time would be 2 ms, which, in theory, sounds great! However, the one-in-a-million person waiting 16 minutes for their search results won't be very happy with Google! (There would probably be less bad press if every search operation just took 5 ms...).

Is there a way we could remove the amortization from the data structure we designed in Approach 2?

For this to happen, we'd need to have each "removal" happen with its corresponding add(); not during some arbitrary showFirstUnique() call in the future. This is the only way we could avoid having lots of "waiting" removal operations. How does this work, though? Didn't we already decide it was too difficult?

  • The trouble with doing the removal in the add() method was that it leads to a worst-case O(N)O(N) search of the queue, and potentially a worst-case O(N)O(N) removal from the middle of a queue—if it's even possible (Java doesn't allow removals from the middle of a queue).

  • Making the actual remove an O(1)O(1) operation isn't too difficult; we simply need to use a LinkedList-based rather than Array-based queue implementation.

  • Searching a LinkedList for a value is still O(N)O(N), though. The only data structures that supports search in O(1)O(1) time are hash-sets and hash-maps. But these don't maintain the input order; aren't we just going around in circles now?

There is another, not so well known, data structure we can use here: LinkedHashSet. Note that in Python, we can use an OrderedDict to achieve the same functionality. If you have never heard of it, have a look at its specs before reading any further. Can you see how it solves our problem?

A LinkedHashSet is a HashSet-LinkedList hybrid. Like a HashSet, items can be found, updated, added, and removed in O(1)O(1) time. In addition, it puts links between the entries to keep track of the order they were added. Whenever an item is removed from the LinkedHashSet, the links are updated to point to the previous and next, just like they are in an ordinary LinkedList.

In essence, a LinkedHashSet is a type of queue that supports O(1)O(1) removals from the middle! This is exactly what we need to solve the problem. We can now do the removal in the add() method, and know that it is O(1)O(1).

Algorithm

Complexity Analysis

Let KK be the length of the initial array passed into the constructor.

Let NN be the total number of items added onto the queue so far (including those from the constructor).

  • Time complexity :

    • constructor: O(K)O(K).

      For each of the KK numbers passed into the constructor, we're making a call to add(). As we will determine below, each call to add() has a cost of O(1)O(1). Therefore, for the KK numbers added in the constructor, we get a total cost of KO(1)=O(K)K \cdot O(1) = O(K).

    • add(): O(1)O(1).

      Like before, we're performing a series of O(1)O(1) operations when add() is called. Additionally, we're also removing the number from the queue if it had been unique, but now no longer is. Seeing as the queue is implemented as a LinkedHashSet, the cost of this removal is O(1)O(1).

      Therefore, we get an O(1)O(1) time complexity for add().

    • showFirstUnique(): O(1)O(1).

      This time around, the implementation for showFirstUnique() is straightforward. It simply checks whether or not the queue contains any items, and if it does, it returns the first one (without removing it). This has a cost of O(1)O(1).

  • Space complexity : O(N)O(N).

    Each number is stored up to once in the LinkedHashSet, and up to once in the HashMap. Therefore, we get an overall space complexity of O(N)O(N).


Report Article Issue

Comments: 18
phoenix1584's avatar
Read More

Adding CPP solutions as well would be really helpful.

4
Show 3 replies
Reply
Share
Report
vanhaxl's avatar
Read More

My solution uses LinkedHashMap

class FirstUnique {
    private Map<Integer, Integer> map;
    public FirstUnique(int[] nums) {
        map = new LinkedHashMap<>();
        for(int x: nums) map.put(x, map.getOrDefault(x, 0) + 1);
    }
    
    public int showFirstUnique() {
        for(int key: map.keySet()){
            if(map.get(key) == 1) return key;
        }
        return -1;
    }
    
    public void add(int value) {
        map.put(value, map.getOrDefault(value, 0) + 1);
    }
}

6
Show 1 reply
Reply
Share
Report
keertsur's avatar
Read More

In the second python solution what is the need of doing self.queue = deque(nums)?? while we are calling add function for every number??
self.queue = deque() will work.

2
Show 1 reply
Reply
Share
Report
here-comes-the-g's avatar
Read More

Instead of map we can use HashSet

class FirstUnique {
    Set<Integer> isUnique = new HashSet<>();
    Set<Integer> q = new LinkedHashSet<>();
    
    public FirstUnique(int[] nums) {
        for(int n: nums){
            this.add(n);
        }
    }
    
    public int showFirstUnique() {
        if(!q.isEmpty()){
            return q.iterator().next();
        }
        return -1;
    }
    
    public void add(int value) {
       if(!isUnique.contains(value)){
           isUnique.add(value);
           q.add(value);
       }
        else {
            q.remove(value);
        }
    }
}

1
Reply
Share
Report
manky's avatar
Read More

I loved the thought process - iterative, crisp, and clear. It does really well to expresses the problem-solving journey.

1
Reply
Share
Report
shivammmm's avatar
Read More

Hey, can someone help me with my cpp solution beats 18%. I tried implementing this using a combination of doubly linked list (supports O(1) delete operation anywhere) and a hashmap to simply store the value -> iterator pairing (so that I know where to delete) . But my solution runtime beats 18% and not more. Not sure where complexity is bad.

list<int> ddl;
unordered_map<int,int> cnt;
unordered_map<int,list<int>::iterator> hm;
FirstUnique(vector<int>& nums) {
    loop(i, nums.size()){
        add(nums[i]);
    }
}

int showFirstUnique() {
    if(ddl.size()==0) return -1;
    list<int>::iterator a = ddl.begin();
    return *(a);
}

void add(int value) {
    if(cnt[value]==0) {
        hm[value] = ddl.insert(ddl.end(), value);
    }
    else {
        if(cnt[value]==1){
            ddl.erase(hm[value]);
        }
    }
    cnt[value]++;
}

According to an article I read, 'Insertion and deletion for doubly linked list at a known position is O(1). However, finding that position is O(n), unless it is the head or tail of the list.' Since I am inserting at the tail always, I assume it should be O(1). I mean even adding N elements to the end of a vector has amortized linear complexity, which translates to amortized constant per-item complexity so I am pretty sure add operation is O(1).
So complexity of
constructor: O(K)

add: O(1)
unordered_map find, add, increment - all O(1)
ddl insert at end of list - O(1)
ddl erase at known position - O(1)

showFirstUnique : Just getting the beginning of ddl and returning value O(1)

Overall most optimal time complexity.

0
Reply
Share
Report
sea0920's avatar
Read More

I don't think this is a good question. If someone doesn't know an unusual DS like LinkedHashSet or LinkedHashMap, he will fail the interview?

0
Show 1 reply
Reply
Share
Report
peterpod94's avatar
Read More

Can someone explain to me why the description makes it look like the queue is not getting dequeued for duplicates? According to this the queue should be [3,5,5,2,3] on last step? Am I missing something?

firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]

0
Reply
Share
Report
i_just_want_a_job_please's avatar
Read More

My answer was originally the 3rd answer, but on one of the 12th testcase: 698 was not first within the dictionary/ set if anyone knows why. I am using Python and it is a version above 3.5 where they should be automatically ordered by their insertion. I ended up having to implement my own doubly linked hashmap.

Edit:
Nvm I found the problem, apparently only dictionaries are ordered by default but not a set. Not sure why, but interesting.
Here's some more info:
https://stackoverflow.com/questions/45581901/are-sets-ordered-like-dicts-in-python3-6

0
Reply
Share
Report
codelitter's avatar
Read More

In approach 3, I think there is no need to put false in the map since there is no remove operation on the queue.

   public void add(int value) {
        if(!map.containsKey(value)){
            map.put(value, true);
            set.add(value);
        }else{
            set.remove(value);
        }
    }

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium